// 顺序表头文件

#include "stdio.h"
#include "malloc.h"

#define LIST_INIT_SIZE 100
#define LISTINCREMENT 10
#define OK 1
#define ERROR 0

typedef int Status;
typedef int ElemType;

typedef struct {
    ElemType *elem;
    int length;
    int listsize;
} SqList;  //顺序表类型定义

Status InitList_Sq(SqList &L) {
    L.elem = (ElemType *) malloc(LIST_INIT_SIZE * sizeof(ElemType));
    if (!L.elem)
        return ERROR;
    L.length = 0;
    L.listsize = LIST_INIT_SIZE;
    return OK;
} // 分配空间，初始化为空表。若空间分配成功，返回OK，否则返回ERROR

Status ListEmpty(SqList L) {
    if (L.length == NULL)
        return OK;
    else
        return ERROR;
} // 判断顺序表是否为空，如果表空返回OK,非空返回ERROR

int GetElem(SqList L, int i, ElemType &e) {
    if (i > L.length || i < 1) {
        //printf("weixu Error\n");
        return ERROR;
    }
    e = L.elem[i - 1];
    return OK;
} // 在顺序表L中获取第i个元素的值并在e中返回。如果输入i不合法，返回ERROR。否则在e中返回对应的元素值，返回OK

int LocateElem_Sq(SqList L, ElemType e) {
    for (int i = 0; i < L.length; i++) {
        if (L.elem[i] == e) {
            return i + 1;
        }
    }
    return 0;
} // 比较顺序表L中第一个于e相等的元素，并返回其位序。若不存在则返回0。

Status ListInsert_Sq(SqList &L, int i, ElemType e) {
    ElemType *newbase;
    if (i < 1 || i > L.length + 1) {
        //printf("weixu Error\n");
        return ERROR;
    }
    if (L.length >= L.listsize) {
        newbase = (ElemType *) realloc(L.elem, (L.listsize + LISTINCREMENT) * sizeof(ElemType));
        if (newbase == NULL)
            return ERROR;
        L.elem = newbase;
        L.listsize = L.listsize + LISTINCREMENT;
    }
    for (int k = L.length - 1; k >= i - 1; k--) {
        L.elem[k + 1] = L.elem[k];
    }
    L.elem[i - 1] = e;
    L.length++;
    return OK;
} // 在顺序表L中实现位序i元素之前插入元素e。需判断输入位序的合法性。如果输入i不合法，返回ERROR。

Status ListDelete_Sq(SqList &L, int i, ElemType &e) {
    if (i < 1 || i > L.length) {
        //printf("weixu Error\n");
        return ERROR;
    }
    e = L.elem[i - 1];
    for (int k = i; i <= L.length - 1; k++) {
        L.elem[k - 1] = L.elem[k];
    }
    L.length--;
    return OK;
} //删除表中第i个元素，并将其值在e中返回。需要判断i的合法性，如果i不合法，返回ERROR。

int ListLength(SqList L) {
    return L.length;
}//返回表L的长度

void ListPrint(SqList L) {
    int f = 0;
    for (int i = 0; i < L.length; ++i) {
        if (f == 0) {
            printf("%d", L.elem[i]);
            f = 1;
        }
        printf(" %d", L.elem[i]);
    }
    printf("\n");
} //打印输出表L中的各个元素